\subsection{Представление чисел}

Люди привыкли к десятичной системе счисления вероятно потому что почти у каждого есть по 10 пальцев.
Тем не менее, число 10 не имеет особого значения в науке и математике.
Двоичная система естествена для цифровой электроники: 0 означает отсутствие тока в проводе и 1 --- его присутствие.
10 в двоичной системе это 2 в десятичной; 100 в двоичной это 4 в десятичной, итд.

Если в системе счисления есть 10 цифр, её \IT{основание} или \IT{radix} это 10.
Двоичная система имеет \IT{основание} 2.

Важные вещи, которые полезно вспомнить:
1) \IT{число} это число, в то время как \IT{цифра} это термин из системы письменности, и это обычно один символ;
2) само число не меняется, когда конвертируется из одного основания в другое: меняется способ его записи (или представления
в памяти).

Как сконвертировать число из одного основания в другое?

Позиционная нотация используется почти везде, это означает что всякая цифра имеет свой вес, в зависимости от её расположения
внутри числа.
Если 2 расположена в самом последнем месте справа, это 2.
Если она расположена в месте перед последним, это 20.

Что означает $1234$?

$10^3 \cdot 1 + 10^2 \cdot 2 + 10^1 \cdot 3 + 1 \cdot 4$ = 1234 или
$1000 \cdot 1 + 100 \cdot 2 + 10 \cdot 3 + 4 = 1234$

Та же история и для двоичных чисел, только основание там 2 вместо 10.
Что означает 0b101011?

$2^5 \cdot 1 + 2^4 \cdot 0 + 2^3 \cdot 1 + 2^2 \cdot 0 + 2^1 \cdot 1 + 2^0 \cdot 1 = 43$ или
$32 \cdot 1 + 16 \cdot 0 + 8 \cdot 1 + 4 \cdot 0 + 2 \cdot 1 + 1 = 43$

Позиционную нотацию можно противопоставить непозиционной нотации, такой как римская система записи чисел
\footnote{Об эволюции способов записи чисел, см.также: \InSqBrackets{\TAOCPvolII{}, 195--213.}}.
Вероятно, человечество перешло на позиционную нотацию, потому что так проще работать с числами (сложение, умножение, итд)
на бумаге, в ручную.

Действительно, двоичные числа можно складывать, вычитать, итд, точно также, как этому обычно обучают в школах,
только доступны лишь 2 цифры.

Двоичные числа громоздки, когда их используют в исходных кодах и дампах, так что в этих случаях применяется шестнадцатеричная
система.
Используются цифры 0..9 и еще 6 латинских букв: A..F.
Каждая шестнадцатеричная цифра занимает 4 бита или 4 двоичных цифры, так что конвертировать из двоичной системы в
шестнадцатеричную и назад, можно легко вручную, или даже в уме.

\begin{center}
\begin{longtable}{ | l | l | l | }
\hline
\HeaderColor шестнадцатеричная & \HeaderColor двоичная & \HeaderColor десятичная \\
\hline
0	&0000	&0 \\
1	&0001	&1 \\
2	&0010	&2 \\
3	&0011	&3 \\
4	&0100	&4 \\
5	&0101	&5 \\
6	&0110	&6 \\
7	&0111	&7 \\
8	&1000	&8 \\
9	&1001	&9 \\
A	&1010	&10 \\
B	&1011	&11 \\
C	&1100	&12 \\
D	&1101	&13 \\
E	&1110	&14 \\
F	&1111	&15 \\
\hline
\end{longtable}
\end{center}

Как понять, какое основание используется в конкретном месте?

Десятичные числа обычно записываются как есть, т.е., 1234. Но некоторые ассемблеры позволяют подчеркивать
этот факт для ясности, и это число может быть дополнено суффиксом "d": 1234d.

К двоичным числам иногда спереди добавляют префикс "0b": 0b100110111
(В \ac{GCC} для этого есть нестандартное расширение языка
\footnote{\url{https://gcc.gnu.org/onlinedocs/gcc/Binary-constants.html}}).
Есть также еще один способ: суффикс "b", например: 100110111b.
В этой книге я буду пытаться придерживаться префикса "0b" для двоичных чисел.

Шестнадцатеричные числа имеют префикс "0x" в \CCpp и некоторых других \ac{PL}: 0x1234ABCD.
Либо они имеют суффикс "h": 1234ABCDh --- обычно так они представляются в ассемблерах и отладчиках.
Если число начинается с цифры A..F, перед ним добавляется 0: 0ABCDEFh.
Во времена 8-битных домашних компьютеров, был также способ записи чисел используя префикс \$, например, \$ABCD.
В книге я попытаюсь придерживаться префикса "0x" для шестнадцатеричных чисел.

Нужно ли учиться конвертировать числа в уме? Таблицу шестнадцатеричных чисел из одной цифры легко запомнить.
А запоминать б\'{о}льшие числа, наверное, не стоит.

Наверное, чаще всего шестнадцатеричные числа можно увидеть в \ac{URL}-ах.
Так кодируются буквы не из числа латинских.
Например:
\url{https://en.wiktionary.org/wiki/na\%C3\%AFvet\%C3\%A9} это \ac{URL} страницы в Wiktionary о слове \q{naïveté}.

\subsubsection{Восьмеричная система}

Еще одна система, которая в прошлом много использовалась в программировании это восьмеричная: есть 8 цифр (0..7) и каждая
описывает 3 бита, так что легко конвертировать числа туда и назад.
Она почти везде была заменена шестнадцатеричной, но удивительно, в *NIX имеется утилита использующаяся многими людьми,
которая принимает на вход восьмеричное число: \TT{chmod}.

\myindex{UNIX!chmod}
Как знают многие пользователи *NIX, аргумент \TT{chmod} это число из трех цифр. Первая цифра это права владельца файла,
вторая это права группы (которой файл принадлежит), третья для всех остальных.
И каждая цифра может быть представлена в двоичном виде:

\begin{center}
\begin{longtable}{ | l | l | l | }
\hline
\HeaderColor десятичная & \HeaderColor двоичная & \HeaderColor значение \\
\hline
7	&111	&\textbf{rwx} \\
6	&110	&\textbf{rw-} \\
5	&101	&\textbf{r-x} \\
4	&100	&\textbf{r-{}-} \\
3	&011	&\textbf{-wx} \\
2	&010	&\textbf{-w-} \\
1	&001	&\textbf{-{}-x} \\
0	&000	&\textbf{-{}-{}-} \\
\hline
\end{longtable}
\end{center}

Так что каждый бит привязан к флагу: read/write/execute (чтение/запись/исполнение).

И вот почему я вспомнил здесь о \TT{chmod}, это потому что всё число может быть представлено как число в восьмеричной системе.
Для примера возьмем 644.
Когда вы запускаете \TT{chmod 644 file}, вы выставляете права read/write для владельца, права read для группы, и снова,
read для всех остальных.
Сконвертируем число 644 из восьмеричной системы в двоичную, это будет \TT{110100100}, или (в группах по 3 бита) \TT{110 100 100}.

Теперь мы видим, что каждая тройка описывает права для владельца/группы/остальных:
первая это \TT{rw-}, вторая это \TT{r--} и третья это \TT{r--}.

Восьмеричная система была также популярная на старых компьютерах вроде PDP-8, потому что слово там могло содержать 12, 24 или
36 бит, и эти числа делятся на 3, так что выбор восьмеричной системы в той среде был логичен.
Сейчас, все популярные компьютеры имеют размер слова/адреса 16, 32 или 64 бита, и эти числа делятся на 4,
так что шестнадцатеричная система здесь удобнее.

Восьмеричная система поддерживается всеми стандартными компиляторами \CCpp{}.
Это иногда источник недоумения, потому что восьмеричные числа кодируются с нулем вперед, например, 0377 это 255.
И иногда, вы можете сделать опечатку, и написать "09" вместо 9, и компилятор выдаст ошибку.
GCC может выдать что-то вроде:\\
\TT{error: invalid digit "9" in octal constant}.

Также, восьмеричная система популярна в Java: когда IDA показывает строку с непечатаемыми символами,
они кодируются в восьмеричной системе вместо шестнадцатеричной.
\myindex{JAD}
Точно также себя ведет декомпилятор с Java JAD.

\subsubsection{Делимость}

Когда вы видите десятичное число вроде 120, вы можете быстро понять что оно делится на 10, потому что последняя цифра это 0.
Точно также, 123400 делится на 100, потому что две последних цифры это нули..

Точно также, шестнадцатеричное число 0x1230 делится на 0x10 (или 16), 0x123000 делится на 0x1000 (или 4096), итд.

Двоичное число 0b1000101000 делится на 0b1000 (8), итд.

Это свойство можно часто использовать, чтобы быстро понять,
что длина какого-либо блока в памяти выровнена по некоторой границе.
Например, секции в \ac{PE}-файлах почти всегда начинаются с адресов заканчивающихся 3 шестнадцатеричными нулями:
0x41000, 0x10001000, итд.
Причина в том, что почти все секции в \ac{PE} выровнены по границе 0x1000 (4096) байт.

\subsubsection{Арифметика произвольной точности и основание}

\index{RSA}
Арифметика произвольной точности (multi-precision arithmetic) может использовать огромные числа,
которые могут храниться в нескольких байтах.
Например, ключи RSA, и открытые и закрытые, могут занимать до 4096 бит и даже больше.

В \InSqBrackets{\TAOCPvolII, 265} можно найти такую идею: когда вы сохраняете число произвольной точности в нескольких байтах,
всё число может быть представлено как имеющую систему счисления по основанию $2^8=256$, и каждая цифра находится
в соответствующем байте.
Точно также, если вы сохраняете число произвольной точности в нескольких 32-битных целочисленных значениях,
каждая цифра отправляется в каждый 32-битный слот, и вы можете считать что это число записано в системе с основанием $2^{32}$.

\subsubsection{Произношение}

Числа в недесятичных системах счислениях обычно произносятся по одной цифре: ``один-ноль-ноль-один-один-...''.
Слова вроде ``десять'', ``тысяча'', итд, обычно не произносятся, потому что тогда можно спутать с десятичной системой.

\subsubsection{Числа с плавающей запятой}

Чтобы отличать числа с плавающей запятой от целочисленных, часто, в конце добавляют ``.0'',
например $0.0$, $123.0$, итд.

